import java.util.Arrays;
import java.util.Random;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = new int[]{6,6,6,6,1};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int left, int right) {
        /**
         * 快速排序-三路归并
         * 使用三路快排*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 三路快排
        // -1 随机选择基准值
        int key = arr[left + new Random().nextInt(right - left + 1)];

        // -2 划分数组
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) { // -不会干扰已划分区间
            if(arr[i] < key) {
                swap(arr, ++l, i++);
            } else if(arr[i] == key) {
                i++;
            } else {
                // -由于交换的元素为未知区间，故不步进
                swap(arr, --r, i);
            }
        }

        // 3 递归
        quickSort(arr, left, l);
        quickSort(arr, r, right);
    }

    public static void swap(int[] arr, int i, int j) {
        /**
         * 交换数组中两个元素*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
